{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**回文子串** 系列问题"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "问题1：找出一个字符串（或者列表）中的所有的回文子串，包括长度为1的子串\n",
    "\n",
    "暴力的方法：\n",
    "找出各种长度的所有的子串，然后查看每个子串是否是回文子串。\n",
    "至于怎么检查是否是回文子串，那就很简单了。\n",
    "对于列表，可以通过reverse()方法对列表逆序排列。\n",
    "但是对列表和字符串都通用的办法则是：s[::-1]\n",
    "\"\"\"\n",
    "\n",
    "def getHuiwen0(s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        huiwen = []\n",
    "        max_l = len(s)\n",
    "        for l in range(1,max_l+1): # 选择子串的长度\n",
    "            for i in range(max_l-l+1): # 找出指定长度的所有子串\n",
    "                sub_s = s[i:i+l]\n",
    "                rev_s = sub_s[::-1]\n",
    "                if sub_s == rev_s:\n",
    "                    huiwen.append(sub_s)\n",
    "        return huiwen\n",
    "    \n",
    "\"\"\"\n",
    "思考一下效率的问题。\n",
    "在获取一个小子串的回文子串之后，怎么得到更大的回文子串呢？\n",
    "一个小回文，只有两边增加相同的字符才能构成更大回文。\n",
    "\"\"\"\n",
    "\n",
    "def getHuiwen1(s):\n",
    "    huiwen = []\n",
    "    def get_bigger_huiwen(index,small_h):\n",
    "        if index>0 and index+len(small_h)<len(s): # 要使的小回文可以向两边扩充1位\n",
    "            if s[index-1] == s[index+len(small_h)]:\n",
    "                bigger_h = s[index-1]+small_h+s[index+len(small_h)]\n",
    "                huiwen.append(bigger_h)\n",
    "                print(bigger_h)\n",
    "                get_bigger_huiwen(index-1,bigger_h) # 把发现的新回文，迭代，寻找更大的回文\n",
    "    #找出种子，种子分两种，长度为1的和长度为2的。\n",
    "    for index,item in enumerate(s):\n",
    "        # 长为1的种子：\n",
    "        huiwen.append(item)\n",
    "        print(\"Seed: \",item)\n",
    "        get_bigger_huiwen(index,item)\n",
    "        # 长度为2的种子：\n",
    "        if index<len(s)-1:\n",
    "            s_2 = s[index:index+2] # 获取长度为2的子串\n",
    "            rev_s_2 = s_2[::-1] # 逆序\n",
    "            if s_2 == rev_s_2:\n",
    "                huiwen.append(s_2)\n",
    "                print(\"Seed: \",s_2)\n",
    "                get_bigger_huiwen(index,s_2)\n",
    "    return huiwen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['a', 's', 'd', 'f', 'd', 'a', 's', 'A', 'A', 's', 'AA', 'dfd', 'sAAs']"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getHuiwen0('asdfdasAAs')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Seed:  a\n",
      "Seed:  s\n",
      "Seed:  d\n",
      "Seed:  f\n",
      "dfd\n",
      "sdfds\n",
      "asdfdsa\n",
      "Seed:  d\n",
      "Seed:  s\n",
      "Seed:  a\n",
      "Seed:  A\n",
      "Seed:  AA\n",
      "aAAa\n",
      "Seed:  A\n",
      "Seed:  a\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['a',\n",
       " 's',\n",
       " 'd',\n",
       " 'f',\n",
       " 'dfd',\n",
       " 'sdfds',\n",
       " 'asdfdsa',\n",
       " 'd',\n",
       " 's',\n",
       " 'a',\n",
       " 'A',\n",
       " 'AA',\n",
       " 'aAAa',\n",
       " 'A',\n",
       " 'a']"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getHuiwen1('asdfdsaAAa')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 3, 2, 1]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1,2,3,4]\n",
    "a[::-1]\n",
    "\n",
    "\"\"\"\n",
    "惊不惊喜，意不意外？\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
